package com.base.listNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName: DeleteDuplicates
 * @Description: 83. 删除排序链表中的重复元素
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
 * 返回同样按升序排列的结果链表
 * @author: li
 * @Date: 2021/8/18 5:33 下午
 */
public class DeleteDuplicates {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode before = head;
        ListNode after = head;

        while (after != null) {
            if (before.val == after.val) {
                after = after.next;
                continue;
            }
            before.next = after;
            before = after;
            after = after.next;
        }
        before.next = null;
        return head;

    }

    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;

        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                //出现相同值，删除后面的结点，但是不移动结点
                //如果相同结点过多，就会多次删除
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;

    }

    public ListNode deleteDuplicates2(ListNode head) {
        /**
         * 82. 删除排序链表中的重复元素 II
         * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
         *
         * 返回同样按升序排列的结果链表。
         *
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         * 二次遍历
         */
        if (head == null) {
            return head;
        }
        // 开辟空间存储重复元素
        List<Integer> list = new ArrayList<>();
        ListNode dummy = new ListNode(Integer.MIN_VALUE, head);
        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                if (!list.contains(cur.val)) {
                    list.add(cur.val);
                }
                cur.next = cur.next.next;
            } else {
                cur = cur.next;

            }
        }
        cur = dummy;
        while (cur.next != null) {
            if (list.contains(cur.next.val)) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;

    }

    public ListNode deleteDuplicates3(ListNode root) {
        /**
         * 82. 删除排序链表中的重复元素 II
         * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
         * 返回同样按升序排列的结果链表。
         * 方法二 ：一次遍历
         */
        if (root == null) {
            return null;
        }

        ListNode dummy = new ListNode(Integer.MIN_VALUE, root);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int tmp = cur.next.val;
                while (cur.next != null && cur.next.val == tmp) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;

    }

    public ListNode deleteDuplicates4(ListNode head) {
        /**
         * 82. 删除排序链表中的重复元素 II
         * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
         * 返回同样按升序排列的结果链表。
         * 方法三 ：递归
         */
        // 递归终止条件
        if (head == null || head.next == null ){
            return head;
        }
        if (head.val!=head.next.val){
             head.next = deleteDuplicates4(head.next);
        }else {
            ListNode move = head.next;
            while (move!=null&&head.val == move.val){
                move =move.next;
            }
            return deleteDuplicates4(move);
        }
        return head;

    }

}
